/*
提交链接:https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/description/
902. 最大为 N 的数字组合
赖德檀 2024/10/5
*/

class Solution {
public:
int f(vector<int>arr,int n,int len,int k,int fe,int fx)
{
    if(len==0) return fx==1?1:0;
    int ans = 0;
    int ct = (n/k)%10;
    if(fx==0)
    ans += f(arr,n,len-1,k/10,1,0);

    if(fe==0)
    {
        for(int x : arr)
        {
            if(x<ct)
            {
                ans += f(arr,n,len-1,k/10,1,1);
            }
            else if(x==ct)
            {
                ans += f(arr,n,len-1,k/10,0,1);
            }
            else
            break;
        }
    }
    else
    {
        ans += arr.size()*f(arr,n,len-1,k/10,1,1);
    }
    return ans;
}

    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        int len=1;
        int ans=0;
        int k=1;
        int t=n/10;
        while(t>0)
        {
            t/=10;
            len++;
            k*=10;
        }
        vector<int>arr;
        for(auto x : digits)
        arr.push_back(stoi(x));
        ans+=f(arr,n,len,k,0,0);
        return ans;
    }
};